P2658 【汽车拉力比赛】

并查集的思路很多人已经讲过了，我这里提供几个并查集方法的（常数）优化

1. 路径压缩&按秩合并

int getf(int x){
    if(f[x]==x) return x;
    return f[x]=getf(f[x]);
}
void unite(int x,int y){
    int fx=getf(x),fy=getf(y);
    if(fx==fy) return;
    if(rk[fx]<rk[fy]) f[fx]=fy;
    else f[fy]=fx;
    if(rk[fx]==rk[fy]) rk[fx]++;
}

路径压缩应该很多人都加了吧。。。

1. 四个方向（上下左右）->两个方向（下右）

边是双向的，而且是网格图，因此是有个层次性的，无需重复地双向都unite

1. 将每个路标的fa与第一个路标的fa比较

可以节约一半的getf

另外，感觉自己的码风还挺好理解的。。。

#include <bits/stdc++.h>
using namespace std;
inline int read(int &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
inline void write(int x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}
const int N=505;
int n,m,f[N*N],ans,rk[N*N],a[N][N],l,r;
vector<int> tag;
inline int hash(int x,int y){
    return (x-1)*m+y;
}
inline int getf(int x){
    if(f[x]==x) return x;
    return f[x]=getf(f[x]); //路径压缩
}
inline void unite(int x,int y){
    int fx=getf(x),fy=getf(y);
    if(fx==fy) return;
    if(rk[fx]<rk[fy]) f[fx]=fy; //按秩合并
    else f[fy]=fx;
    if(rk[fx]==rk[fy]) rk[fx]++;
}
inline bool check(int k){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            f[hash(i,j)]=hash(i,j),rk[hash(i,j)]=1; //并查集初始化
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            if(abs(a[i][j]-a[i+1][j])<=k&&i+1<=n) //向下unite(hash(i,j),hash(i+1,j));
            if(abs(a[i][j]-a[i][j+1])<=k&&j+1<=m) //向右 unite(hash(i,j),hash(i,j+1));
        }
    int fa=getf(tag[0]); //先得到第一个fa
    for(int i=1;i<tag.size();i++) if(getf(tag[i])!=fa) //后面的与第一个比较
        return 0;
    return 1;
}
signed main(){
    read(n);read(m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            read(a[i][j]);
            r=max(r,a[i][j]);
        }
    for(int i=1;i<=n;i++)
        for(int j=1,x;j<=m;j++){
            read(x);
            if(x) tag.push_back(hash(i,j)); //我用vector存路标
        }
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)) r=mid-1,ans=mid;
        else l=mid+1;
    }
    write(ans);
}

另外，我这份代码是用c++交的，c++11以上会ce